package _16_设计;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _352_将数据流变为多个不相交区间 {

    public static void main(String[] args) {
        _352_将数据流变为多个不相交区间 v = new _352_将数据流变为多个不相交区间();

        v.addNum(6);
        v.addNum(6);
        v.addNum(4);
        v.addNum(8);
        v.addNum(7);
        v.addNum(6);
        v.addNum(4);
        v.addNum(7);
        v.addNum(5);

        int[][] intervals = v.getIntervals();

        for (int[] interval : intervals) {
            System.out.println(Arrays.toString(interval));
        }

    }

    // 存放数据流，如果对于排序数据流来说，查找插入位置的话，需要挪动元素位置，这样效率比较低
    private final List<Integer> list;

    private int length;

    public _352_将数据流变为多个不相交区间() {
        list = new ArrayList<>();
    }

    public void addNum(int val) {
        // 从有序数组中查找插入位置
        int searchIndex = binarySearchInsertIndex(val);
        if (length == 0 || searchIndex >= length || list.get(searchIndex) != val) {
            list.add(searchIndex, val);
            length++;
        }
    }

    public int[][] getIntervals() {
        ArrayList<int[]> results = new ArrayList<>();
        // 返回连续区间
        int left = list.get(0);
        int right;
        for (int i = 1; i < length; i++) {
            if (list.get(i) - list.get(i - 1) <= 1) {
                continue;
            }
            right = list.get(i - 1);
            results.add(new int[]{left, right});
            left = list.get(i);
        }
        results.add(new int[]{left, list.get(length - 1)});
        return results.toArray(new int[results.size()][2]);
    }

    // 二分法，查找插入位置
    private int binarySearchInsertIndex(int val) {
        int left = 0;
        int result = list.size();
        int right = result - 1;
        // 找到第一个大于，当前值
        while (left <= right) {
            // 防止数据溢出
            int mid = left - ((left - right) >> 1);
            if (list.get(mid) >= val) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }


}
